// https://leetcode.cn/problems/single-number-ii/description/

// 算法思路总结：
// 1. 使用位统计法解决只出现一次的数字
// 2. 创建32位数组统计每位1的出现次数
// 3. 遍历所有数字，统计每位上的1的个数
// 4. 对每位统计结果模3，余数为1的位组成结果
// 5. 时间复杂度：O(32n)，空间复杂度：O(32)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int hash[32] = {0}, ret = 0;
        for (const int& num : nums)
        {
            for (int i = 0 ; i < 32 ; i++)
            {
                if (num & (1 << i))
                    hash[i]++;
            }
        }

        for (int i = 0 ; i < 32 ; i++)
        {
            if (hash[i] % 3)
                ret |= 1 << i;
        }
        return ret;
    }
};

int main()
{
    vector<int> v1 = {2,2,3,2}, v2 = {0,1,0,1,0,1,99};

    Solution sol;
    cout << sol.singleNumber(v1) << endl;
    cout << sol.singleNumber(v2) << endl;

    return 0;
}